package com.learn.bigtalkdatastructure.e.string;

import org.junit.Test;

import java.util.Arrays;

/**
 * 5.7 KMP模式匹配算法
 *
 * @author robin
 * @since 2018/11/7 22:34
 */
public class KMP {

    /**
     * 推导给定字符串的Next数组，用于KMP算法
     *
     * @param T
     *
     * @return
     */
    private static int[] generateNextArray(String T) {
        int[] result = new int[T.length()];
        String[] t = T.split("");

        for (int j = 0; j < T.length(); j++) {
            if (j == 0) {
                result[j] = 0;
                continue;
            } else if (j == 1) {
                result[j] = 1;
                continue;
            }

            String sub = T.substring(0, j);

            String[] subArray = sub.split("");

            for (int i = 1; i <= subArray.length; i++) {
                String left = sub.substring(0, sub.length() - i);
                String right = sub.substring(i, sub.length());

                if (left.equals(right)) {
                    result[j] = sub.length() - i + 1;
                    break;
                }

                if (i == sub.length()) {
                    result[j] = 1;
                    break;
                }
            }
        }

        return result;
    }


    public static void main(String[] args) {
        int[] next = generateNextArray("aaaaaaaab");
        Arrays.stream(next).forEach(System.out::println);
    }

}
